/*************************************************************************
 * File Name:    Palindrome_Partitioning_II.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: Sun 02 Jun 2013 09:57:10 PM CST
 * 
 * Description:  
 |------------------------------------------------------------------------
 | Problem : Palindrome Partitioning II 
 |
 | Given a string s, partition s such that every substring of the partition 
 | is a palindrome.
 |
 | Return the minimum cuts needed for a palindrome partitioning of s.
 |
 | For example, given s = "aab",
 | Return 1 since the palindrome partitioning ["aa","b"] could be produced
 | using 1 cut.
 |------------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <list>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

class Solution {
public:
    int minCut(string s)
    {
        bool palind[s.size()][s.size()];
        int dp[s.size()];

        for (size_t k = 1; k <= s.size(); ++k) {
            for (size_t i = 0; i + k <= s.size(); ++i) {
                palind[i][i + k - 1] = (s[i] == s[i + k - 1]);

                if (k > 2) {
                    palind[i][i + k - 1] = palind[i][i + k - 1] && palind[i + 1][i + k - 2];
                }
            }
        }

        for (size_t i = 0; i < s.size(); ++i) {
            if (palind[0][i]) {
                dp[i] = 1;
                continue;
            }

            dp[i] = dp[i - 1] + 1;
            for (size_t j = 1; j < i; ++j) {
                if (palind[j][i]) {
                    dp[i] = min(dp[i], dp[j - 1] + 1);
                }
            }
        }

        return dp[s.size() - 1] - 1;
    }
};

int
main(int argc, char *argv[])
{
    string s;
    Solution sol;

    while (cin >> s) {
        cout << sol.minCut(s) << endl;
    }

    return 0;
}
